The invention relates to compression of image data and, more particularly, concerns the compressed representation of an image by means of a plurality of rectangular image portions defined over a scanned representation of the image.
The increased capacity of information communication systems has amplified the demand for storage and transfer of many varieties of information, including text, graphics images, and video images. However, demands for availability of data limit processing time and require speedy response by storage and processing facilities. Compression of data is widely employed to reduce data processing time.
A great number of techniques have been developed to compress graphical and video images for storage and transmission. Most of these techniques are based upon scanned, digitized image presentations in which a plurality of picture elements (pixels) are arrayed into a two-dimensional matrix, each pixel location corresponding to a particular location in an image. These presentations are "scanned" or "rasterized" in the sense that they are assembled or output in order beginning with the top left-most pixel, moving horizontally to the end of the first row of pixels, and continuing until the bottom right-most pixel is encountered, at which time the scanning process retraces to the beginning, and so on.
In virtually all display systems which employ digital technology, a scanned image is generated from a memory with a plurality of memory locations in a two-dimensional array corresponding to that of the image's pixel array. Each memory location holds a pixel value representing intensity of one or more colors to be displayed at the corresponding pixel location. Inherently, the array of memory locations establishes an array of pixel values; this array is a two-dimensional image representation in which each pixel value corresponds precisely with a pixel location. Each pixel value is represented by a multi-bit digital word.
Many of the techniques developed for compressing the image information contained in an array of pixel values actually involve two steps. In the first step, the total information in the array is compressed. In the second step, the compressed two-dimensional representation is encoded into a compressed information stream for transmission. The invention discussed in the following detailed description is concerned essentially with the first step, that is with compression of the information contained in a two-dimensional pixel array before the array is encoded for transmission.
One known technique for pixel value array compression, called "contour encoding", partitions the pixel values into closed, interlocking regions. A region consists of a subset of the array in which pixel values are substantially equal. Compression results for two reasons. First, the number of symbols required to encode the perimeter of the subset is typically smaller than the number of symbols required to encode all of the pixel values the subset contains. Second, since the pixel values are substantially equal, each value need not be encoded; instead, a single value can be encoded for the entire subset.
While the contour encoding technique can result in significant compression of the information in a two-dimensional pixel value array, it has recently been determined that such information can be compressed even further by partitioning a pixel value array into a plurality of rectangular regions in each of which variance between pixel values is less than some threshold. Each region is encoded simply by its x and y dimensions and a value level which is the average of all pixel values within the region.
While these prior techniques provide significant reductions in information entropy or "lossy-ness" within a two-dimensional pixel value array, they are intended essentially for encoding static images ("still frames"). None of these techniques has been adapted for encoding video images in which change of image features (motion) constitutes a significant portion of the image information.